#include <stdio.h>
#include <stdlib.h>
#include <string.h>

#define MAX_HEAP 0
#define MIN_HEAP 1
#define swap(a,b) {a=a+b; b=a-b; a=a-b;}

typedef struct {
	int *arr;
	int capacity;
	int count;
	int heap_type;
} heap;

void heap_init(heap *h, int type, int capacity) 
{
	h->heap_type = type;
	h->capacity = capacity;
	h->count = 0;
	h->arr = malloc(sizeof(int) * h->capacity);
}

int node_parent(heap *h, int i)
{
	if (i <= 0 || i >= h->count) return -1;
	return (i-1)/2;
}

int node_left_child(heap *h, int i)
{
	int left = 2*i + 1;
	if (left >= h->count) return -1;
	return left;
}

int node_right_child(heap *h, int i)
{
	int right = 2*i + 2;
	if (right >= h->count) return -1;
	return right;
}

int top_val(heap *h)
{
	if (h->count == 0) return -1;
	return h->arr[0];
}

//父与子节点比较，i为父节点位置，返回最大节点位置
int index_of_max(heap *h, int i) 
{
	int l, r, max = i;
	l = node_left_child(h, i);
	r = node_right_child(h, i);
	
	//如果left_child存在, 则i先和left_child比较
	if (l != -1 && h->arr[l] > h->arr[max])	max = l;
	if (r != -1 && h->arr[r] > h->arr[max])	max = r;

	return max;
}
/* 调整i位置上的元素，向下渗透 */
void percolate_down(heap *h, int i)
{
	int max = index_of_max(h, i);
	if (max == i) return;	//父节点不小于子节点，下沉结束
	
	swap(h->arr[max], h->arr[i]);
	percolate_down(h, max);	
}

int heap_del(heap *h)
{
	int val;
	if (h->count == 0) return -1;
	val = h->arr[0]; //取出top
	h->arr[0] = h->arr[h->count - 1]; //将末尾节点放到top位置
	h->count--; //删除末尾节点
	percolate_down(h, 0); //调整top位置的元素
	return val;
}

void heap_resize(heap *h)
{
	int i, *arr_old = h->arr;	//指向原来的数据
	
	h->arr = (int *)malloc(sizeof(int) * h->capacity*2); 
	if (h->arr == NULL) {
		printf("memory error.");
		return ;
	}

	memcpy(h->arr,arr_old,sizeof(int)*h->capacity);
	h->capacity *= 2;
	free(arr_old);
}

void heap_insert(heap *h, int val)
{
	int i, parent;
	if (h->count == h->capacity) 
		heap_resize(h);
	h->count++;
	i = h->count - 1; //arr[len - 1] = val; 
	while (i >= 0 && val > h->arr[(i-1)/2]) {
		h->arr[i] = h->arr[(i-1)/2];
		i = node_parent(h, i);
	}
	h->arr[i] = val;
}


void heap_destory(heap *h) 
{
	free(h->arr);
	h->count = 0;
}

void heap_build(heap *h, int arr[], int n)
{
	int i;
	//if (h == NULL) return ;
	while (n > h->capacity) 
		heap_resize(h);

	//可以直接拷贝整个数组到h->arr，再percolate_down调整
	//也可以一个一个地插入
	memcpy(h->arr, arr, sizeof(int)*n);
	h->count = n;

	for (i = (n-1)/2; i >= 0; i--)
		percolate_down(h, i);
}

// 不改变原arr数组，返回一个新的有序数组，malloced。
// 或直接调整h->arr为正常有序数组。
int *heap_sort(int arr[], int n)
{
	heap h;
	int i, t, len;
	int *num = malloc(sizeof(int)*n);
	heap_init(&h, MAX_HEAP, n);
	heap_build(&h, arr, n);

	len = h.count;
	for (i = 0; i < len; i++) {
		//printf("%d ",heap_del(&h));
		num[i] = heap_del(&h);
	}
	return num;
}

void main()
{
	int i,a[10]={27,70,33,82,100,29,5,14,33,50};
	int len = 10;
	int *num = heap_sort(a,len);
	for(i=0; i<len; i++)
		printf("%d ", num[i]);
}